import java.lang.*;
import java.io.*;


/**
 * This was an implementation that I found on the web
 *
 */
public class StringBinTree implements Serializable{
	private StringBinTree root;
	
	public StringBinTree left,right;
    public String data;
    // Misc vars just to add size
    private Double l1 = new Double(Math.random());
    private Double l2 = new Double(Math.random());
    private Double l3 = new Double(Math.random());
    private Double l4 = new Double(Math.random());
    

    public static StringBinTree tree_AddString(StringBinTree r,String s){
    	
        if(r == null){
            r = new StringBinTree();
            r.left = r.right = null;
            r.data = s;
        }else if(r.data.compareTo(s) < 0)
            r.right = tree_AddString(r.right,s);
        else
            r.left = tree_AddString(r.left,s);

        
        return r;
    }

    public void tree_InOrderPrint(StringBinTree r){
        if(r != null){
            tree_InOrderPrint(r.left);
            System.out.print(" "+r.data);
            tree_InOrderPrint(r.right);
        }
    }
    
    public void tree_Serialize(StringBinTree r, ObjectOutput os) throws IOException 
    {
        if(r != null){
            os.writeUTF(r.data);
        	tree_Serialize(r.left, os);
            tree_Serialize(r.right, os);
        }
    }

    public static void tree_FileWrite(
        StringBinTree r,
        DataOutputStream output) throws IOException{
        if(r != null){
            byte[] tmp = r.data.getBytes();
            output.writeInt(tmp.length);
            output.write(tmp);
            tree_FileWrite(r.left,output);
            tree_FileWrite(r.right,output);
        }else
            output.writeInt(0);
    }

    public static StringBinTree tree_FileRead(
        StringBinTree r,
        DataInputStream input) throws IOException{
        int n = input.readInt();
        if(n != 0){
            byte[] tmp = new byte[n];
            input.read(tmp);
            r = new StringBinTree();
            r.data = new String(tmp);
            r.left = tree_FileRead(r.left,input);
            r.right = tree_FileRead(r.right,input);
        }else
            r = null;
        return r;
    }

    public static boolean tree_Compare(
        StringBinTree a,StringBinTree b){
        if(a != null && b != null){
            return a.data.compareTo(b.data) == 0 &&
                tree_Compare(a.left,b.left) &&
                tree_Compare(a.right,b.right);
        }else if(a == null && b == null)
            return true;
        else
            return false;
    }
}
